/*
 * @lc app=leetcode.cn id=1345 lang=typescript
 *
 * [1345] 跳跃游戏 IV
 */

// @lc code=start
function minJumps(arr: number[]): number {
  const n = arr.length;
  // 记录相同元素的索引
  const hash = new Map<number, number[]>();
  for (let i = 0; i < n; i++) {
    const key = arr[i];
    if (!hash.has(key)) hash.set(key, []);
    hash.get(key).push(i);
  }

  const visited = new Set<number>();
  visited.add(0);
  const deque = new Array<number[]>();
  deque.push([0, 0]);

  while (deque.length) {
    let [idx, step] = deque.shift();
    if (idx === n - 1) {
      return step;
    }

    step++;
    // 将相同元素的索引放入队列，避免后面重复计算
    const val = arr[idx];
    if (hash.has(val)) {
      for (const i of hash.get(val)) {
        if (!visited.has(i)) {
          visited.add(i);
          deque.push([i, step]);
        }
      }
      hash.delete(val);
    }
    // 是否可以往后走一步
    if (idx + 1 < n && !visited.has(idx + 1)) {
      visited.add(idx + 1);
      deque.push([idx + 1, step]);
    }
    // 是否可以往前走一步
    if (idx - 1 >= 0 && !visited.has(idx - 1)) {
      visited.add(idx - 1);
      deque.push([idx - 1, step]);
    }
  }

  return -1;
}
// @lc code=end
